package advance.day06;


import java.util.ArrayList;
import java.util.LinkedList;

/**
 * 描述：
 *      判断是否是一颗完全二叉树
 * @author hl
 * @version 1.0
 * @date 2020/11/12 10:54
 */
public class IsCBT {
    public boolean isCBT(Node head){
        if (head == null) {
            return true;
        }
        Node cur = head;
        boolean leaf = false;
        LinkedList<Node> queue = new LinkedList<>();
        queue.addLast(cur);
        Node left = null;
        Node right = null;
        while(!queue.isEmpty()){
            Node curNode = queue.pollFirst();
            left = curNode.left;
            right = curNode.right;
            if ((leaf && (left != null || right != null))
            || (right != null && left == null)) {
                return false;
            }
            //能进入下面代码的情况只有两种：1）左右孩子双全 2）左右都为空 3）左不为空，右为空
            if (left != null) {
                queue.addLast(left);
            }
            if(right != null){
                queue.addLast(right);
            }else{
                //第2）、3）种情况下开启都是叶子结点阶段
                leaf = true;
            }
        }
        return true;
    }

    public static void main(String[] args) {

    }
}
